const division = function (list, left, right) {
  // 以最左边的数(left)为基准
  let base = list[left];
  while (left < right) {
    // 从序列右端开始，向左遍历，直到找到小于base的数
    while (left < right && list[right] >= base)
      right--;
    // 找到了比base小的元素，将这个元素放到最左边的位置
    list[left] = list[right];

    // 从序列左端开始，向右遍历，直到找到大于base的数
    while (left < right && list[left] <= base)
      left++;
    // 找到了比base大的元素，将这个元素放到最右边的位置
    list[right] = list[left];
  }

  // 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
  // 而left位置的右侧数值应该都比left大。
  list[left] = base;
  return left;
}

const quickSort = function (list, left, right) {

  // 左下标一定小于右下标，否则就越界了
  if (left < right) {
    // 对数组进行分割，取出下次分割的基准标号
    let base = division(list, left, right);
    // 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
    quickSort(list, left, base - 1);

    // 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
    quickSort(list, base + 1, right);
  }

  return list;
}

let quickSort1 = arr => {
  if (arr.length < 1) return arr;
  let left = [];
  let right = [];
  let baseIndex = Math.floor(arr.length / 2);
  let base = arr.splice(baseIndex, 1)[0];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] <= base) left.push(arr[i]);
    else right.push(arr[i]);
  }
  return quickSort1(left).concat([base], quickSort1(right));
}

let arr = [2, 0, 2, 1, 8, 7, 0, 3, 6, 1, 9];
console.log(quickSort1(arr))

